//package test;
//
//class Pair<K, V> {
//    public K key;
//    public V val;
//
//    public Pair(K key, V val) {
//        this.key = key;
//        this.val = val;
//    }
//
//    public K getKey() {
//        return key;
//    }
//
//    public void setKey(K key) {
//        this.key = key;
//    }
//
//    public V getVal() {
//        return val;
//    }
//
//    public void setVal(V val) {
//        this.val = val;
//    }
//}
//
//class TreeNode {
//    public int[] keys;
//    public TreeNode subs;
//    public TreeNode parent;
//    public int usedsize;
//
//    public TreeNode(int M) {
//        this.keys = new int[M];
//        this.subs = new TreeNode(M + 1);
//    }
//}
//
//public class MyBtree {
//    public static final int M = 3;
//    public TreeNode root;
//
//    //插入一个元素
//    public boolean insert(int key) {
//        //B树为空的时候
//        if (root == null) {
//            root = new TreeNode(M);
//            root.keys[0] = key;
//            root.usedsize++;
//            return true;
//        }
//        //当B树不为空的时候，我们需要查看当前B树当中，是否存在我的Key
//        Pair<TreeNode, Integer> pair = find(key);
//        //判断这里获取到的val值是不是-1 来确定当前是否存在该key
//        if (pair.getVal() != -1) {
//            return false;
//        }
//        TreeNode parent = pair.getKey();
//        int index = parent.usedsize - 1;
//        for (; index >= 0; index--) {
//            if (parent.keys[index] >= key) {
//                parent.keys[index + 1] = parent.keys[index];
//            } else {
//                break;
//            }
//        }
//        parent.keys[index + 1] = key;
//        parent.usedsize++;
//
//        if (parent.usedsize > M) {
//            return true;
//        } else {
//            split(parent);
//        }
//        return false;
//    }
//
//    public void split(TreeNode parent) {
//
//    }
//
//    public Pair<TreeNode, Integer> find(int key) {
//        TreeNode cur = root;
//        TreeNode parent = null;
//        while (cur != null) {
//            int i = 0;
//            while (i < cur.usedsize) {
//                if (cur.keys[i] == key) {
//                    //返回当前找到的节点和当前这个数据在节点当中的下标
//                    return new Pair<>(cur, i);
//                } else if (cur.keys[i] < key) {
//                    i++;
//                } else {
//                    break;
//                }
//            }
//            parent = cur;
//            cur = cur.subs[i];
//        }
//        return new Pair<>(parent, -1);
//    }
//}
